Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods

摘要

In this paper, we study matrix scaling and balancing, which are fundamentalproblems in scientific computing, with a long line of work on them that datesback to the 1960s. We provide algorithms for both these problems that, ignoringlogarithmic factors involving the dimension of the input matrix and the size ofits entries, both run in time $\widetilde{O}\left(m\log \kappa \log^2(1/\epsilon)\right)$ where $\epsilon$ is the amount of error we are willing totolerate. Here, $\kappa$ represents the ratio between the largest and thesmallest entries of the optimal scalings. This implies that our algorithms runin nearly-linear time whenever $\kappa$ is quasi-polynomial, which includes, inparticular, the case of strictly positive matrices. We complement our resultsby providing a separate algorithm that uses an interior-point method and runsin time $\widetilde{O}(m^{3/2} \log (1/\epsilon))$. In order to establish these results, we develop a new second-orderoptimization framework that enables us to treat both problems in a unified andprincipled manner. This framework identifies a certain generalization of linearsystem solving that we can use to efficiently minimize a broad class offunctions, which we call second-order robust. We then show that in the contextof the specific functions capturing matrix scaling and balancing, we canleverage and generalize the work on Laplacian system solving to make thealgorithms obtained via this framework very efficient.